package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC334 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean increasingTriplet(int[] arr) {
            if (null == arr || arr.length < 3) {
                return false;
            }

            int[] curMin = new int[arr.length];
            int[] curMax = new int[arr.length];
            for (int i = 0; i < arr.length; i++) curMin[i] = i == 0 ? arr[0] : Math.min(curMin[i - 1], arr[i]);
            for (int i = arr.length - 1; i >= 0; i--)
                curMax[i] = i == arr.length - 1 ? arr[arr.length - 1] : Math.max(curMax[i + 1], arr[i]);

            for (int i = 1; i < arr.length - 1; i++) {
                if (curMin[i - 1] < arr[i] && arr[i] < curMax[i + 1]) return true;
            }

            return false;
        }
    }


    class Solution_Time_Exceed {
        public boolean increasingTriplet(int[] arr) {
            if (null == arr || arr.length < 3) {
                return false;
            }

            for (int i = 1; i < arr.length - 1; i++) {
                boolean before = false;
                boolean after = false;

                for (int j = 0; j < i; j++) {
                    if (arr[j] < arr[i]) {
                        before = true;
                        break;
                    }
                }

                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] > arr[i]) {
                        after = true;
                        break;
                    }
                }

                if (before && after) {
                    return true;
                }
            }

            return false;
        }
    }


    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.increasingTriplet(InputUtil.toIntegerArray("[1,2,3]")));
        System.out.println(solution.increasingTriplet(InputUtil.toIntegerArray("[2,1,5,0,4,6]")));
        System.out.println(solution.increasingTriplet(InputUtil.toIntegerArray("[5,4,3,2,1]")));
    }

    public static void main(String[] args) throws Exception {
        LC334 an = new LC334();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
